#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>

using namespace std;

class Solution
{
public:
    static vector<int> findSubstring(string s, vector<string> &words)
    {
        //优化前
        // vector<int> ret;
        // unordered_map<string, int> hash2; // 用于记录words子串的哈希表
        // for (auto i : words)
        // {
        //     if (hash2.find(i) == hash2.end()) // 说明此时里面没有这个字符串
        //     {
        //         hash2.insert({i, 1}); // 此时就对这个字符串进行插入
        //     }
        //     else // 说明此时哈希表里面已经有了这个字符串
        //     {
        //         hash2[i]++; // 直接对这个位置进行++
        //     }
        // }
        // // 此时hash2里面就已经记录号words的情况了
        // int n = words[0].size();                // 这个就是目标数组中每个字符串的长度了
        // for (int begin = 0; begin < n; begin++) // 因为存在n种滑动情况，所以使用for循环来处理
        // {
        //     unordered_map<string, int> hash1; // 用于记录s子串的哈希表
        //     int cnt = 0; // 有效字符串数
        //     for (int left = begin, right = begin + n - 1 /*right此时一定在第一个字符串的末尾处*/;
        //          right < s.size() - ((s.size() - begin) % n); right += n) // 将这个字符串进行拆分
        //     {
        //         // 进窗口
        //         string str2 = s.substr(right - n + 1, n); // right为末尾的长度为n的字符串str
        //         if (hash1.find(str2) == hash1.end())
        //         {
        //             // 说明此时没有找到
        //             hash1.insert({str2, 1});
        //         }
        //         else
        //         {
        //             // 说明此时找到了
        //             hash1[str2]++;
        //         }
        //         if (hash2.find(str2) != hash2.end()) // 进窗口后对cnt进行维护
        //         {
        //             if (hash1[str2] <= hash2[str2])
        //                 cnt++;
        //         }
        //         if (right - left + 1 > words.size() /*目标字符串的总个数*/ * n /*单个字符串的长度*/) // 判断
        //         {
        //             string str1 = s.substr(left, n); // 从left处开始的长度为n的字符串
        //             // 出窗口前维护cnt
        //             if (hash2.find(str1) != hash2.end())
        //             {
        //                 // cout << hash1[str1] << endl;
        //                 if (hash1[str1] <= hash2[str1])
        //                     cnt--;
        //             }
        //             // 出窗口
        //             hash1[str1]--;
        //             if (hash1[str1] == 0) // 此时为空了，就将这个位置的节点删除
        //             {
        //                 hash1.erase(str1);
        //             }
        //             left += n;
        //         }
        //         if (cnt == words.size())
        //         {
        //             ret.push_back(left);
        //         }
        //     }
        // }
        // return ret;
        //优化后：代码更简洁了，但是运行速度更慢了？？？空间更大了？？？
        vector<int> ret;
        unordered_map<string, int> hash2; // 用于记录words子串的哈希表
        for (auto i : words)
        {
            hash2[i]++; // 直接对这个位置进行++
        }
        // 此时hash2里面就已经记录号words的情况了
        int n = words[0].size();                // 这个就是目标数组中每个字符串的长度了
        for (int begin = 0; begin < n; begin++) // 因为存在n种滑动情况，所以使用for循环来处理
        {
            unordered_map<string, int> hash1; // 用于记录s子串的哈希表
            for (int left = begin, right = begin, cnt = 0; right + n <= s.size(); right += n) // 将这个字符串进行拆分
            {
                // 进窗口
                string str2 = s.substr(right, n); // right为末尾的长度为n的字符串str
                hash1[str2]++;
                if (hash1.count(str2) && hash1[str2] <= hash2[str2])
                    cnt++;
                if (right - left + 1 > words.size() /*目标字符串的总个数*/ * n /*单个字符串的长度*/) // 判断
                {
                    string str1 = s.substr(left, n); // 从left处开始的长度为n的字符串
                    // 出窗口前维护cnt
                    if (hash1.count(str1) && hash1[str1] <= hash2[str1])
                        cnt--;
                    // 出窗口
                    hash1[str1]--;
                    left += n;
                }
                if (cnt == words.size())
                {
                    ret.push_back(left);
                }
            }
        }
        return ret;
    }
};

int main()
{
    string s = "barfoothefoobarman";
    vector<string> p = {"foo", "bar"};
    // string s = "wordgoodgoodgoodbestword";
    // vector<string> p = {"word","good","best","word"};
    // string s = "barfoofoobarthefoobarman";
    // vector<string> p = {"bar","foo","the"};
    // string s = "ababaab";
    // vector<string> p = {"ab", "ba", "ba"};
    // string s = "abcbdefghiabcbde";
    // vector<string> p = {"bcb","def","abc","bde","ghi"};
    vector<int> ans = Solution::findSubstring(s, p);
    for (auto i : ans)
    {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}